//
// Created by Jisam on 21/09/2024 8:00 PM.
// Solution of   求欧拉函数
#include <bits/stdc++.h>
#define  int long long
using namespace std;
int phi(int x)
{
    int res = x;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res = res / i * (i - 1);
            while (x % i == 0) x /= i;
        }
    if (x > 1) res = res / x * (x - 1);

    return res;
}
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    int ma = 0;
    for(int i = 0 ; i < n ; i ++){
        cin  >> a[i];
        cout << phi(a[i]);
    }

    return 0;
}